Un système de file d'attente consiste d'un ou de plusieurs serveurs qui fournissent un service d'une certaine nature à des clients qui se présentent. Les clients qui arrivent et trouvent tous les serveurs occupés rejoindront (généralement) une ou plusieurs files (ou lignes) devant les serveurs, d'où la qualification de file d'attente.
Le système de file d'attente est caractérisé par trois composants:
Spécifier le processus d'arrivée pour un système de file d'attente revient à décrire comment les clients arrivent dans le système. Soit $A_i$ le temps d'inter-arrivées entre les arrivées des $(i-1)^e$ et $i^e$ clients. Si $A_1$, $A_2,\ldots$, sont supposés être des variables i.i.d., nous dénoterons le temps d'interarrivée moyen (ou espéré) par $E[A]$ et appellerons $\lambda = 1/E[A]$ le taux d'arrivée des clients.
Le mécanisme de service pour un système de file d'attente est articulé en spécifiant le nombre de serveurs (dénoté par $s$), où chaque serveur a sa propre file ou au contraire une seule file alimente tous les serveurs, et la distribution de probabilité des temps de service des clients.
Soit $S_i$ le temps de service du $i^e$ client. Si $S_1,\ldots$ sont des variables aléatoires i.i.d., nous dénoterons le temps de service moyen d'un client par $E[S]$ et appelleront $\omega = 1/E[S]$ le taux de service d'un serveur.
En d'autres termes, le premier client arrivé dans la file est le premier servi. La discipline de file réfère à la manière dont un serveur choisit le prochain client à partir d'une file (s'il en existe une) quand le serveur termine le service du client courant. Les disciplines courantes sont
En général, nous supposerons que le mécanisme est de tye FIFO: first-in first-out.
Il est d'usage d'utiliser la notation introduite par David George Kendall en 1953, de forme A/S/C où A décrit le temps entre les arrivées dans la file, S le temps de service et C le nombre de serveurs. La notation a par la suite été étendue à 6 paramètres, mais nous ne considérons que la version à 3 paramètres. Supposons en particulier que
Un tel système sera dénoté une file $GI/G/s$, où $GI$ (general independant) réfère à la distribution des $A_i$ et $G$ (general) réfère à la distribution des $S_i$. Si des distributions spécifiques sont données pour les $A_i$ et les $S_i$, des symboles dénotant ces distributions sont utilisés en place de $GI$ et de $G$. En particulier, le symbole $M$ est utilisé pour la distribution exponentielle en raison de son caractère markovien, i.e. la propriété sans mémoire. La lettre $D$ est employée pour des temps déterministes, ou en d'autres termes constants. $s$ désigne le nombre de serveurs. Dés lors, un système de file d'attente avec un seul serveur et des temps d'inter-arrivées et de service exponentiels, et une discipline de file FIFO, est appelé file $M/M/1$.
Pour n'importe quelle file $GI/G/s$, nous appellerons la quantité $$ \rho = \frac{\lambda}{s\omega} $$ le facteur d'utilisation du système de file d'attente ($s\omega$ est le taux de service quand tous les serveurs sont occupés). C'est une mesure de l'importance d'utilisation des ressources du système de file d'attente.
Il existe de nombreuses mesures de performance possibles pour les systèmes de file d'attente; parmi celles-ci, nous en retiendrons quatre fréquemment utilisées pour les études mathématiques de tels systèmes. Posons
Les mesures $$ w = \lim_{n \rightarrow \infty} \frac{\sum_{i = 1}^n W_i}{n} \quad \mbox{a.p. 1}, \quad \mbox{et} \quad d = \lim_{n \rightarrow \infty} \frac{\sum_{i = 1}^n D_i}{n} \quad \mbox{a.p. 1}, $$ si elles existent, sont appelées délai moyen en état stable et temps d'attente moyen en état stable. Similairement, les mesures $$ q = \lim_{T \rightarrow \infty} \frac{\int_0^T q(t) dt}{T} \quad \mbox{a.p. 1}, \quad \mbox{et} \quad L = \lim_{T \rightarrow \infty} \frac{\int_0^T L(t) dt}{T} \quad \mbox{a.p. 1}, $$ si elles existent, sont appelées nombre moyen par unité de temps en état stable dans la file, et nombre moyen par unité de temps en état stable dans le système.
Notons que $\rho < 1$ est une condition nécessaire pour que $d$, $w$, $q$ et $L$ existent pour une file d'attente $GI/G/1$. Dans ce cas, si $d$ et $w$ existent, nous avons les équations de conservation $$ q = \lambda w \quad \mbox{et} \quad L = \lambda d. $$ Une autre égalité d'intérêt pratique est donnée par $$ d = w+E[S], $$ et donc $$ q = L - \rho. $$ Dans le cas d'une file $M/M/1$, nous pouvons en outre montrer que le nombre moyen en état stable dans le système est donné par $$ L = \frac{\rho}{1-\rho}. $$
La loi de Little dit que le nombre moyen $N$ de clients dans un système stable (ou sur un horizon infini), est égal à leur fréquence moyenne d'arrivée $\lambda$, multipliée par leur temps moyen $T$ passé dans le système: $$ N = \lambda T $$ L'équation est valable sous des conditions assez générales. Encore faut-il que le système soit en état stable!